Fast and Feasible: Permutation-based Constrained Reranking for Revenue Maximization
快速可行的基于排列的约束重排序以实现收益最大化
🧭 约束优化重排序 · 排列近似算法 ★ 深度解读
Avito · MSU, AI Center
提出 PermR 排列邻域搜索算法，在 0.05 秒内近似求解收益最大化 ILP，线上收入提升 2%
📌 工作参考价值（4 点）
- 重排序建模为 ILP：以当前生产排序的指标值作为约束下界，保证可行且不显著损害用户体验，可直接借鉴到电商搜索重排场景。
- 排列邻域搜索算法 PermR：通过交换相邻商品提升目标或修复约束，复杂度极低（≤0.05s），适合线上实时部署；采样概率由商品得分差驱动，清晰可复现。
- 位置偏置使用指数衰减（γ_j = 0.97^j）计算曝光收益，可按平台实际曝光率拟合；多条约束可定义在不同截断前缀（如 top-5 相关度），适应分屏业务需求。
- 离线/在线验证流程：先离线评估 ILP 最优上限、确定 PermR 迭代次数（如 750），再上线 A/B（14 天，56M 查询），最终收益 +2%，适合作为搜索/推荐重排模块的落地范本。